package demo1;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //x的平方根
    public int mySqrt(int x) {
        int left = 1;
        int right = x;
        while (left < right) {
            int mid = left+(right-left+1)/2;
            if (mid * mid <= left * left) {
                left = mid;
            }else {
                right = mid-1;
            }
        }
        return left;
    }

    //在排序数组中查找元素的第一的位置和最后一个位置
    public int[] searchRange(int[] nums, int target) {
        int[] ret = new int[2];
        ret[0] = ret[1] = -1;
        if (nums.length == 0) {
            return ret;
        }
        int left = 0;
        int rigth = nums.length-1;
        while (left < rigth) {
            int mid = left+(rigth-left)/2;
            if (nums[mid] < target) {
                left = mid+1;
            }else {
                rigth = mid;
            }
        }
        if(nums[rigth] != target){
            return ret;
        }
        ret[0] = rigth;
        left = 0;
        rigth = nums.length-1;
        while (left < rigth) {
            int mid = left+(rigth-left+1)/2;
            if (nums[mid] <= target) {
                left = mid;
            }else {
                rigth = mid-1;
            }
        }
        ret[1] = left;
        return ret;
    }
}
